package lru;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: javase
 * @description: LRU缓存
 * @author: luolidong
 * @create: 2021-07-06 09:34
 * @version: 1.0
 */
public class Lru2 {
    class Node<k, v> {
        k key;
        v value;
        Node<k, v> prev;
        Node<k, v> next;

        public Node() {
        }

        public Node(k key, v value) {
            this.key = key;
            this.value = value;
        }
    }

    class DoubleLinkedList<k, v> {
        Node<k, v> head;
        Node<k, v> tail;


        public DoubleLinkedList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }

        /**
         * @Description: 添加到头
         * @Param: [node]
         * @return: void
         */
        public void insertNode(Node<k, v> node) {
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
            node.prev = head;
        }

        /**
         * @Description: 删除结点
         * @Param: [node]
         * @return: void
         */
        public void deleteNode(Node<k, v> node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.next = null;
            node.prev = null;
        }

        /**
         * @Description: 获取尾结点，删除的时候要用
         * @Param: []
         * @return: lru.Lru2.Node
         */
        public Node getLastNode() {
            return tail.prev;
        }
    }

    private int capacity;
    private Map<Integer, Node<Integer, Integer>> map;
    private DoubleLinkedList<Integer, Integer> list;

    public Lru2(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList<>();
    }
    /**
    * @Description: 获取
    * @Param: [key]
    * @return: int
    */
    public int get(int key) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            //调整顺序
            list.deleteNode(node);
            list.insertNode(node);
            return node.value;
        }
        return -1;
    }
    /**
    * @Description: 添加
    * @Param: [key, value]
    * @return: void
    */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            //key已经存在
            Node<Integer, Integer> node = map.get(key);
            node.value = value;//修改value
            //先删除再插入
            list.deleteNode(node);
            list.insertNode(node);
            map.put(key, node);
        } else {
            if (map.size() >= capacity) {//容量已满
                //先获取尾结点，在删除
                Node lastNode = list.getLastNode();
                list.deleteNode(lastNode);
                //删除map中的尾结点 key
                map.remove(lastNode.key);
            }
            //没有满,添加新节点
            Node<Integer, Integer> newNode = new Node<>(key, value);
            list.insertNode(newNode);
            map.put(key, newNode);
        }
    }

    public static void main(String[] args) {
        Lru2 lru2 = new Lru2(3);
        lru2.put(1, 1);
        lru2.put(2, 1);
        lru2.put(3, 1);
        lru2.put(4, 1);

        System.out.println("lru2.get(3) = " + lru2.get(3));

        lru2.put(5, 1);
        Node<Integer, Integer> head = lru2.list.head;
        while (head.next!=lru2.list.tail){
            System.out.println(head.next.key);
            head=head.next;
        }
    }
}
